package com.gwcloud.leetcode.hot100;

import java.util.Arrays;

/** 
* @ClassName   : Leetcode0279 
* @author      : ganwei 
* @date        : 2020年5月23日 
* @Description : 完全平方数 
*/
public class Leetcode0279 {
	/**
	 * -解题思路
	 */
    public int numSquares(int n) {
    	int dp[] = new int[n+1];
    	Arrays.fill(dp, Integer.MAX_VALUE);
    	
    	dp[0] = 0;
        int max_square_index = (int) Math.sqrt(n) + 1;
        int square_nums[] = new int[max_square_index];

        for (int i = 1; i < max_square_index; ++i) {
            square_nums[i] = i * i;
        }

        
        for(int i = 1; i <= n; i++) {
        	for(int s = 1; s < max_square_index; s++) {
        		if(i < square_nums[s]) {
        			break;
        		}
        		dp[i] = Math.min(dp[i], dp[i-square_nums[s]]+1);
        	}
        }
    	return dp[n];
    }
    
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	Leetcode0279 l0279 = new Leetcode0279();
    	System.out.println(l0279.numSquares(12));
    }
}
